1. Field of the Invention
This invention relates to data processing systems in general, and to packet switching systems in particular. More particularly, this invention relates to sorting networks for use in, for example, asynchronus transfer mode (ATM) switch controllers or computer coprocessors.
2. Prior Art of the Invention
In ATM packet switching networks internal buffering is often used to resolve output contention, such as in a buffered Banyan network. An alternative to buffering is the use of sorting networks, the most well-known of which is the Batcher bitonic sorter as implemented, for example, in Batcher-Banyan networks.
In general, in communication systems and computer systems it may often be either necessary or desirable to sort signals received by the system. The sorting results in the system distinguishing, for example, signals of higher priority from signals of lower priority. The priority of a signal may be established on the basis, for example, of the magnitude of a particular constituent of it.
Prior art sorters have comprised sets of sub-stages of sorter cells forming sorting modules which increase in size, by a factor of two per stage. Such prior art sorters perform a binary merge operation on pairs of sorted lists. The connection patterns between stages and sub-stages in such prior art sorters are highly regular but are best implemented in a 3-dimensional way, since projections onto a plane requires a large amount of space for such sorters. Such sorters require three or four interconnection layers to accommodate the crossing signals and clock/power. Because of such interconnection topology it is not possible to remove a fractional part of the Batcher sorter.